package com.swak.algs;

/**
 * 二分查找
 * 
 * 有序数组来查询一个数 <br>
 * 相邻的两个数不相同的列表来查询局部最小<br>
 * 
 * @author lifeng
 */
public class Code07 {

	/*
	 * 通过最简单的查找来查询一个数据
	 */
	static int search(int[] arr, int num) {
		for (int i = 0; i <= arr.length - 1; i++) {
			if (arr[i] == num) {
				return i;
			}
		}
		return -1;
	}

	/*
	 * 通过二分查找的方式来查找
	 */
	static int search01(int[] arr, int num) {
		int N = arr.length;
		int L = 0;
		int R = N - 1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (arr[mid] == num) {
				return mid;
			} else if (arr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}
		return -1;
	}

	/*
	 * 最左: = 莫个数
	 */
	static int search02(int[] arr, int num) {
		int N = arr.length;
		int L = 0;
		int R = N - 1;
		int tag = -1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (arr[mid] == num) {
				tag = mid;

				// 如果最左则
				R = mid - 1;

				// 如果最右
				// L = mid + 1;
			} else if (arr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}

		/*
		 * 返回最后一次相等
		 */
		return tag;
	}

	/*
	 * 最右: = 莫个数
	 */
	static int search03(int[] arr, int num) {
		int N = arr.length;
		int L = 0;
		int R = N - 1;
		int tag = -1;
		while (L <= R) {
			int mid = (L + R) / 2;
			if (arr[mid] == num) {
				tag = mid;

				// 如果最左则
				// R = mid - 1;

				// 如果最右
				L = mid + 1;
			} else if (arr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}

		/*
		 * 返回最后一次相等
		 */
		return tag;
	}

	/*
	 * 最接近
	 */
	static int search04(int[] arr, int num) {
		int N = arr.length;
		int L = 0;
		int R = N - 1;
		int tag = -1;
		while (L <= R) {
			int mid = (L + R) / 2;
			tag = mid;
			if (arr[mid] == num) {
				R = mid - 1;
			} else if (arr[mid] > num) {
				R = mid - 1;
			} else {
				L = mid + 1;
			}
		}

		/*
		 * 返回最后一次相等
		 */
		return tag;
	}

	public static void main(String[] args) {
		int[] arr = { 1, 4, 4, 6, 6, 8, 9, 10, 12, 15, 38 };
		System.out.println(search(arr, 6));
		System.out.println(search01(arr, 6));
		System.out.println(search02(arr, 6));
		System.out.println(search03(arr, 6));
		System.out.println(search04(arr, 7));
	}
}
